package com.cheng.learn.leetcode;

/**
 * @description: find the peek element of array（找到数组的峰值，力扣：162题）
 *
 * @author: ChengHaiZhu
 * @create: 2021-03-15 00:22
 **/
public class FindPeekElement162 {

    /**
     * 方法一： 时间复杂度是 O(n),空间复杂度是O(1)
     * @param nums
     * @return
     */
    public int findPeakElement1(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            // 只要遇到一个比后一个大的数，就是峰值
            if (nums[i] > nums[i + 1])
                return i;
        }
        // 如果没有前一个比后一个大，说明是递增序列
        return nums.length - 1;
    }

    /**
     * 方法二：
     * @param nums
     * @return
     */
    public int findPeakElement2(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }

    /**
     * 方法三：时间复杂度是O(logN),空间复杂度是O(1),
     * @param nums
     * @return
     */
    public int findPeakElement3(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
}
